package structure.algorithm.sort;

/**
 * 插入排序原理
 * 1.从第一个元素开始，该元素可以认为已经被排序
 * 2.取出下一个元素，在已经排序的元素序列中从后向前扫描
 * 3.如果该元素（已排序）大于新元素，将该元素移到下一位置
 * 4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
 * 5.将新元素插入到该位置后
 * 6.重复步骤2~5
 * @author fidel
 */
public class InsertSort {
    public static void sort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }
        // 声明并动态初始化一个长度与array相同的新数组并将array的第一个元素置于新数组中
        int[] newArray = new int[array.length];
        newArray[0] = array[0];
        for (int index = 1; index < array.length; index++) {
            // value：预排序的数组中索引值为index的元素值
            // index，indexValue：索引值
            int value = array[index], indexValue = index;
            /*
             * 当value小于新数组从右数第一个数值时，将后者在数组中的索引值向后移动一位
             * 再比较新数组从右数第二个数值，依此类推
             */
            while (value < newArray[indexValue - 1]) {
                int t = newArray[indexValue];
                newArray[indexValue] = newArray[indexValue - 1];
                newArray[indexValue - 1] = t;
                indexValue -= 1;
                // 当索引值为0时，说明已遍历到新数组最左侧
                if (indexValue == 0) {
                    break;
                }
            }
            // 新数组中元素的排列顺序是有序的
            newArray[indexValue] = value;
        }
        System.arraycopy(newArray, 0, array, 0, array.length);
    }
}
